﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace BoggleSolver {
    public enum Match {
        Perfect,
        Partial,
        None
    }
    class Boggle {

        bool[][] used;
        int nRows, nCols;
        string[] grid;
        List<string> results;
        List<string> dict;
        public List<string> SolveBoggle(string [] sGrid, List<string> words) {
            dict = words;
            grid = sGrid;
            nRows = grid.Length;
            nCols = grid[0].Length;

            used = new bool[nRows][];
            for (int i = 0; i < nRows; i++)
                used[i] = new bool[nCols];

            results = new List<string>();

            for (int rowPos = 0; rowPos < nRows; rowPos++)
                for (int colPos = 0; colPos < nCols; colPos++)
                    SolveCase(used, rowPos, colPos, string.Empty);

            return results;
        }

        private void SolveCase(bool[][] used, int x, int y, string current) {
            Match match = SearchMatch(dict, current);
            if (match != Match.None) {
                string newChain = current + grid[x][y];
                if (current.Length > 2 && match == Match.Perfect && !results.Contains(current))
                    results.Add(current);

                for (int xModif = -1; xModif <= 1; xModif++) {
                    for (int yModif = -1; yModif <= 1; yModif++) {
                        if (x + xModif >= 0 && x + xModif < nRows && y + yModif >= 0 && y + yModif < nCols && !(xModif == 0 && yModif == 0)) {
                            if (!used[x + xModif][y + yModif]) {
                                used[x][y] = true;
                                SolveCase(used, x + xModif, y + yModif, newChain);
                                used[x][y] = false;
                            }
                        }
                    }
                }
            }
        }

        public Match SearchMatch(List<string> words, string s) {
            int start;
            int end;
            int middle;

            start = 0;
            end = words.Count;
            Match match = Match.None;

            List<string> partialMatches = new List<string>();
            while ((end - start) > 1) {

                middle = (start + end) / 2;
                string tempWord = words[middle];
                string target = s;
                if (s.Length < words[middle].Length)
                    tempWord = words[middle].Substring(0, s.Length);

                if (tempWord == target) {
                    if (s == words[middle]) {
                        return Match.Perfect;
                    }
                    else {
                        partialMatches.Add(words[middle]);
                        match = Match.Partial;
                    }
                }
                if (words[middle].CompareTo(s) > 0)
                    end = middle;
                else
                    start = middle;
            }
            return match;
        }
    }
}
